home *** CD-ROM | disk | FTP | other *** search
/ QRZ! Ham Radio 8 / QRZ Ham Radio Callsign Database - Volume 8.iso / pc / files / t_unix / j109lxa4.tar / bootpdip.c < prev    next >
C/C++ Source or Header  |  1994-06-04  |  30KB  |  1,028 lines
  1. /*
  2.  * Center for Information Technology Integration
  3.  *           The University of Michigan
  4.  *                    Ann Arbor
  5.  *
  6.  * Dedicated to the public domain.
  7.  * Send questions to info@citi.umich.edu
  8.  * BOOTP is documented in RFC 951 and RFC 1048
  9.  *
  10.  * Delinted, ANSIfied and reformatted - 5/30/91 P. Karn
  11.  */
  12.  
  13.  
  14.  
  15. /* Dynamic Ip Assignment for a Bootp Server
  16.  * Called when a client request is received and the bootp server doesnt' have a
  17.  * record for it.
  18.  *
  19.  * Design goals:
  20.  *   Assign an IP address
  21.  *   Separation/Identification of IP addresses assigned and not assigned
  22.  *   Time out mechanism to reclaim IP address
  23.  *    Timer, and arp on address with little activity
  24.  *   Reassignment to same machine if possible.
  25.  */     
  26. #include <stdio.h>
  27. #include <time.h>    
  28.  
  29. #include "global.h"
  30. #include "arp.h"
  31. #include "iface.h"
  32. #include "mbuf.h"
  33. #include "netuser.h"
  34. #include "pktdrvr.h"
  35. #include "timer.h"
  36. #include "bootpd.h"
  37.  
  38.  
  39. #define E_NOMEM 3101
  40. #define ERR_NOIPADDRESS    3103        /* No IP address available. */
  41.  
  42. #define THRESH_ON            20    /* (%) When to turn on reclaimation of IP addresses. */
  43. #define THRESH_CRITICAL       2    /* (#) */
  44. #define THRESH_OFF           50    /* (%) */
  45.  
  46. #define R_OFF                   0x01    /* Reclaimation is off. */
  47. #define R_RECLAIM               0x02    /* Reclaimation is on. */
  48. #define R_CRITICAL              0x04    /* Reclaimation is operating in critical state. */
  49. #define R_DONE                  0x08    /* Reclaimation is finishing up. */
  50. #define V_SWAIT                 0x10    /* Reclaimation is wait to start verif cycle. */
  51. #define V_VERIFY                0x20    /* Reclaimation is in verification cycle. */
  52.  
  53. #define TIME_RWAIT        (5)     /* Time between running reclm da_task */
  54. #define TIME_SWAIT              (30)    /* Time between cycles of starting address rec */
  55. #define TIME_VWAIT              (10)    /* Time to wait between sending ARPs to verify add
  56. resses. */
  57. #define TIME_ADDRRETRY          (4 * 600)       /* Time to wait before trying to reclaim a
  58. n address. */
  59. #define TIME_ADDRRECLAIM        (900)   /* Time for which an address must be in the reclai
  60. mation */
  61.                                         /* queue before being moved to the free list. */
  62.  
  63. #define RECLAIM_QUEUE_MAX       15      /* Maximum number of addresses in reclaimation queue. */
  64.  
  65.  
  66.  
  67. /*      dynamic_ip.c
  68.  *
  69.  * This file contains code to manage a range of dynamic IP addresses on a network.
  70.  */
  71.     
  72.  
  73.  
  74. /* Queue structures  */
  75.  
  76. #ifndef __GNUC__
  77. /* was this supposed to accomplish something???  ++bsa */
  78. typedef
  79. #endif
  80. struct  q_elt {
  81.         struct  q_elt *next;
  82. };
  83.  
  84. #define NULLQ_ELT (struct q_elt *) 0
  85.  
  86.  
  87. struct  q {
  88.         char *head;
  89.         char *tail;
  90. };
  91.  
  92. #define NULLQ_P (struct q *) 0
  93.  
  94.  
  95. /* Dynamic IP structures */
  96.  
  97. struct daddr {
  98.         struct daddr    *da_next;       /* Queue link. */
  99.         int32        da_addr;        /* IP address. */
  100.         time_t        da_time;        /* last time this address was answered for. */
  101.     char        da_hwaddr[1];   /* Hardware address, variable length. */
  102. };
  103.  
  104. #define NULLDADDR (struct daddr *) 0
  105.  
  106. struct drange_desc {
  107.         struct drange_desc *dr_next;    /* Queue link. */
  108.         struct iface    *dr_iface;      /* Pointer to network information. */
  109.     struct timer    timer;        /* Timer for reclaiming */
  110.         int32        dr_start;       /* First IP address in range. */
  111.         int32        dr_end;         /* Last IP address in range. */
  112.         int16           dr_acount;      /* Number of IP addresses in range. */
  113.         int16           dr_fcount;      /* Number of IP addresses in free. */
  114.         int16           dr_rcount;      /* Number of IP addresses on reclmation queue  */
  115.         int16           dr_thon;        /* Threshold for turning on reclaimation. */
  116.         int16           dr_thcritical;  /* Threshold for critical reclaimation. */
  117.         int16           dr_thoff;       /* Threshold for turning off reclaimation. */
  118.         int32           dr_time_addrretry;      /* Time to wait before retrying addresses.
  119.                            Varies with state. */
  120.         int16           dr_hwaddrlen;   /* Length of hardware address. */
  121.         unsigned char   dr_rstate;      /* Reclaimation state. */
  122.         unsigned char   dr_vstate;      /* Verification state. */
  123.         time_t          dr_rtime;       /* Time stamp for reclaimation. */
  124.         struct daddr    *dr_raddr;      /* Address being verified. */
  125.         struct daddr    *dr_table;      /* Pointer to table of addresses. */
  126.         struct q        dr_usedq;       /* Pointer to list of used addresses. */
  127.         struct q        dr_reclaimq;    /* Pointer to list of addrs being reclaimed.  */
  128.         struct q        dr_freeq;       /* Pointer to list of free addresses. */
  129. };
  130.  
  131. #define NULLDRANGE (struct drange_desc *) 0
  132.  
  133.  
  134.  
  135.  
  136.  
  137. #define da_structlen(dr)        (sizeof (struct daddr) + dr->dr_hwaddrlen)
  138. #define da_getnext(dr,da)       ((struct daddr *) ((unsigned char *)da + da_structlen(dr)))
  139.  
  140.  
  141. /*
  142.  * Globals.
  143.  */
  144.  
  145. int ifaceToArpMap[] = {
  146.         0,                                 /* CL_NONE */
  147.         ARP_ETHER,                             /* CL_ETHERNET */
  148.         ARP_PRONET,                             /* CL_PRONET_10 */
  149.         ARP_IEEE802,                            /* CL_IEEE8025 */
  150.         0,                                 /* CL_OMNINET */
  151.         ARP_APPLETALK,                          /* CL_APPLETALK */
  152.         0,                                   /* CL_SERIAL_LINE */
  153.         0,                                 /* CL_STARLAN */
  154.         ARP_ARCNET,                             /* CL_ARCNET */
  155.         ARP_AX25,                               /* CL_AX25 */
  156.         0,                                      /* CL_KISS */
  157.         0,                                      /* CL_IEEE8023 */
  158.         0,                                      /* CL_FDDI */
  159.         0,                                      /* CL_INTERNET_X25 */
  160.         0,                                      /* CL_LANSTAR */
  161.         0,                                      /* CL_SLFP */
  162.         ARP_NETROM,                             /* CL_NETROM */
  163.         0                                       /* NCLASS */
  164. };
  165.  
  166.  
  167.  
  168. static struct q                 rtabq;
  169. struct timer            da_timer;
  170. char                bp_ascii[128];
  171.  
  172. static void da_runtask __ARGS((void *arg));
  173. struct q_elt *q_dequeue __ARGS((struct q *queue));
  174. static void da_closeup __ARGS((struct drange_desc *dr));
  175. static void dprint_addresses __ARGS((struct drange_desc *dr));
  176. static int q_remove __ARGS((struct q *source_queue,struct q_elt *qel));
  177. static void iptoa __ARGS((int32 ipaddr,char ipstr[16]));
  178. static void da_task __ARGS((void));
  179. static int da_fill_reclaim __ARGS((struct drange_desc *dr));
  180. static void da_do_verify __ARGS((struct drange_desc *dr,int pendtime));
  181. static void da_enter_reclaim __ARGS((struct drange_desc *dr));
  182. static void da_enter_done __ARGS((struct drange_desc *dr));
  183. static void da_enter_off __ARGS((struct drange_desc *dr));
  184. static void q_enqueue __ARGS((struct q     *queue,struct q_elt *elem));
  185. static int da_get_old_addr __ARGS((struct drange_desc *dr,char *hwaddr,struct daddr **dap));
  186. static int da_get_free_addr __ARGS((struct drange_desc *dr,struct daddr **dap));
  187. static void da_enter_critical __ARGS((struct drange_desc *dr));
  188. static void q_init __ARGS((struct q *queue));
  189.  
  190. extern int bp_ReadingCMDFile;
  191.  
  192.  
  193.  
  194. /*
  195.  * Shutdown routines.
  196.  */
  197.  
  198. /*
  199.  * Done serving a network.
  200.  */
  201. int
  202. da_done_net(iface)
  203. struct iface *iface;
  204. {
  205.         struct drange_desc *dr;
  206.  
  207.         /* Find the network table */
  208.         for(dr = (struct drange_desc *) rtabq.head; dr != NULLDRANGE; dr = dr->dr_next){
  209.                 if(iface == dr->dr_iface)
  210.                         break;
  211.         }
  212.  
  213.         if(dr == NULLDRANGE){
  214.         bp_log("Range for interface '%s' not found.\n", iface->name);
  215.         return -1;
  216.     }
  217.  
  218.         da_closeup(dr);
  219.     bp_log("Range removed for iface %s\n", iface->name);
  220.         return 0;
  221. }
  222.  
  223.  
  224.  
  225.  
  226. /*
  227.  * Print the status of the da structures.
  228.  */
  229. void
  230. da_status(iface)
  231. struct iface *iface;
  232. {
  233.         struct drange_desc *dr;
  234.  
  235.     /* If no interface was specified, print all the range information */
  236.     if(iface == NULLIF){
  237.             for(dr = (struct drange_desc *) rtabq.head; dr != NULLDRANGE; 
  238.          dr = dr->dr_next) 
  239.             dprint_addresses(dr);
  240.     
  241.     } else {
  242.         /* Print the specified range's information */
  243.         /* Find the specified interface */
  244.             for(dr = (struct drange_desc *) rtabq.head; 
  245.          (dr != NULLDRANGE) && (dr->dr_iface != iface); 
  246.          dr = dr->dr_next)
  247.             ; 
  248.         
  249.         /* If network not found, return */
  250.         if(dr == NULLDRANGE){
  251.             tprintf("Range for interface '%s' not found.\n", iface->name);
  252.             return;    
  253.         }
  254.         /* The range has been found.  Print it. */
  255.         dprint_addresses(dr);
  256.     }
  257. }
  258.  
  259.  
  260.  
  261. /*
  262.  * Finish up service.  Close up on each of the address ranges.
  263.  */
  264. void
  265. da_shut()
  266. {
  267.         struct drange_desc *dr;
  268.  
  269.     stop_timer(&da_timer);
  270.         while((dr = (struct drange_desc *)q_dequeue (&rtabq)) != NULLDRANGE)
  271.                 da_closeup(dr);
  272. }
  273.  
  274.  
  275. /*
  276.  * Release resource for a network.
  277.  */
  278. static void
  279. da_closeup(dr)
  280. struct drange_desc *dr;
  281. {
  282.         free(dr->dr_table);            /* Free the address table. */
  283.         q_remove(&rtabq, (struct q_elt *)dr);    /* Dequeue the range descriptor. */
  284.         free(dr);                /* Free the range descriptor. */
  285. }
  286.  
  287.  
  288.  
  289. /* This is only called from a command */
  290. static void
  291. dprint_addresses(dr)
  292. struct drange_desc *dr;
  293. {
  294.         struct daddr *da;
  295.         char ipa[16];
  296.     char ipb[16];
  297.     struct arp_type    *at;
  298.     
  299.     at = &Arp_type[dr->dr_iface->type];
  300.  
  301.     iptoa(dr->dr_start, ipa);
  302.     iptoa(dr->dr_end, ipb);
  303.     tprintf("Interface %s range: %s - %s\n", dr->dr_iface->name, ipa, ipb);
  304.  
  305.         da = (struct daddr *) dr->dr_freeq.head;
  306.     tprintf("Free address queue\n");
  307.         while(da){
  308.                 iptoa(da->da_addr, ipa);
  309.                 tprintf("    %s  last used by %s\n", ipa,(*at->format)(bp_ascii, da->da_hwaddr));
  310.                 da = da->da_next;
  311.         }
  312.  
  313.         da = (struct daddr *) dr->dr_usedq.head;
  314.         tprintf("\nUsed address queue\n");
  315.         while(da){
  316.                 iptoa(da->da_addr, ipa);
  317.                 tprintf("    %s  in use by %s\n", ipa, (*at->format)(bp_ascii, da->da_hwaddr));
  318.                 da = da->da_next;
  319.         }
  320.  
  321.         da =(struct daddr *) dr->dr_reclaimq.head;
  322.         tprintf("\nReclaimation address queue\n");
  323.         while(da){
  324.                 iptoa(da->da_addr, ipa);
  325.                 tprintf("    %s  in use by %s?\n", ipa, (*at->format)(bp_ascii, da->da_hwaddr));
  326.                 da = da->da_next;
  327.         }
  328.         tprintf("\n");
  329. }
  330.  
  331.  
  332.  
  333. /*
  334.  * Reclaimation routines.
  335.  */
  336. static void
  337. da_runtask(p)
  338. void *p;
  339. {
  340.     stop_timer(&da_timer);
  341.     da_task();
  342.     set_timer(&da_timer,TIME_RWAIT*1000L);
  343.     start_timer(&da_timer);
  344. }
  345.  
  346. /*
  347.  * Called periodically to run reclaimation.
  348.  */
  349. static void
  350. da_task()
  351. {
  352.     struct drange_desc *dr;
  353.     time_t now;
  354.     int arpHardware, arpPendtime;
  355.  
  356.     now = time(NULL);
  357.  
  358.     for(dr = (struct drange_desc *)rtabq.head; dr != NULLDRANGE; dr = dr->dr_next){
  359.  
  360.         arpHardware = ifaceToArpMap [dr->dr_iface->type];
  361.         arpPendtime = Arp_type[arpHardware].pendtime;
  362.  
  363.         if(!(dr->dr_rstate & R_OFF)){    /* If doing reclaimation on this range. */
  364.             if(dr->dr_vstate == V_SWAIT){    /* If in wait sub-state. */
  365.                 /* Doing reclaimation on this range and am waiting to 
  366.                  * start a cycle of address
  367.                  * verification.  Check if it is time to start the 
  368.                  * cycle. */
  369.  
  370.                 if(now - dr->dr_rtime > TIME_SWAIT){
  371.                     /* Start the cycle.  */
  372.                     if(!(dr->dr_rstate & R_DONE))
  373.                         da_fill_reclaim(dr);
  374.  
  375.                     dr->dr_vstate = V_VERIFY; /* verify sub-state. */
  376.                     dr->dr_raddr = NULLDADDR; /* start at beginning */
  377.                 }
  378.             }
  379.             /* If in the verify state (may have just been changed above), and 
  380.              * enough time has passed since last lookup, check it and start
  381.              * the next lookup. */
  382.  
  383.             if(dr->dr_vstate == V_VERIFY){
  384.                 if(now - dr->dr_rtime > arpPendtime){
  385.                     da_do_verify(dr, arpPendtime); /* Verify address. */
  386.                     dr->dr_rtime = time(NULL); /* Set time stamp. */
  387.                     if(dr->dr_raddr == NULLDADDR){ /* If at end... */
  388.                         dr->dr_vstate = V_SWAIT; /* Q empty; enter wait sub-state. */
  389.                     }
  390.                 }
  391.             }
  392.             
  393.             /* 
  394.              * State transitions.  May have moved some addresses to free list.
  395.              * If so, I may be able to move to a "lower" state.
  396.              */
  397.             switch(dr->dr_rstate){
  398.             /* case R_OFF: Not handled. */
  399.             case R_CRITICAL:
  400.                 /* Have conditions droped below critical threshhold? */
  401.                 if(dr->dr_fcount > dr->dr_thcritical)    
  402.                     da_enter_reclaim(dr);
  403.                 /* Fall through. */
  404.             case R_RECLAIM:
  405.                 /* Have I reclaimed enough addresses? */
  406.                 if(dr->dr_fcount > dr->dr_thoff)    
  407.                     da_enter_done(dr);
  408.                 /* Fall through. */
  409.             case R_DONE:
  410.                 /* Am I in the done state and have exausted the reclaimation queue? */
  411.                 if((dr->dr_rstate & R_DONE) && dr->dr_reclaimq.head == NULLCHAR) 
  412.                     da_enter_off(dr);
  413.                 break;
  414.             }
  415.         }
  416.     }
  417. }
  418.  
  419.  
  420.  
  421.  
  422. /* 
  423.  * Enter the DONE state.  Can't get to the done state from the off state.
  424.  */
  425. static void
  426. da_enter_done(dr)
  427. struct drange_desc *dr;
  428. {
  429.     char ipa[16], ipb[16];
  430.     
  431.     iptoa(dr->dr_start, ipa);
  432.     iptoa(dr->dr_end, ipb);
  433.  
  434.     if((dr->dr_rstate & R_OFF) == 0){ 
  435.         dr->dr_rstate = R_DONE;
  436.         dr->dr_time_addrretry = TIME_ADDRRETRY;        /* Wait a while before retrying addresses. */
  437.     }
  438. }
  439.  
  440.  
  441. /* 
  442.  * Enter the OFF state.
  443.  */
  444. static void
  445. da_enter_off(dr)
  446. struct drange_desc *dr;
  447. {
  448.     char ipa[16], ipb[16];
  449.     
  450.     iptoa(dr->dr_start, ipa);
  451.     iptoa(dr->dr_end, ipb);
  452.  
  453.     dr->dr_rstate = R_OFF;
  454. }
  455.  
  456.  
  457. /*
  458.  * Verify addresses.
  459.  * To avoid flodding the network and our address resolution queue I only send
  460.  * out one ARP at a time.  This routine is called periodically to step through
  461.  * the reclaimation queue.  The first step is to check for a responce to the
  462.  * ARP that was sent out previously.  If there is a responce I move the address
  463.  * to the used queue. The next step is to send out an ARP for the next address
  464.  * on the recliamation queue. After a suitable intervel (TIME_VTIME) I'll be
  465.  * called again.
  466.  */
  467. static void
  468. da_do_verify(dr, pendtime)
  469. struct drange_desc *dr;
  470. int pendtime;
  471. {
  472.     struct daddr *da, *dn;
  473.     struct iface *iface;
  474.     long now;
  475.     struct arp_tab *ap;
  476.     int16 arpType;
  477.     
  478.      now = time(NULL);
  479.      iface = dr->dr_iface;
  480.     arpType = ifaceToArpMap[iface->type];
  481.  
  482.     /*
  483.       * If I sent an ARP for an address, check if that ARP has been responded to.
  484.      * If dr_raddr points to an address record, I have previously sent an
  485.      * ARP for that address.  Check the ARP cache for a responce.
  486.      * If dr_raddr is NULL then I am to start at the head of the reclaim queue.
  487.       */
  488.  
  489.     if(dr->dr_raddr != NULLDADDR){
  490.         /* ARP has been sent for dr_raddr.  Check the ARP cache for a responce. */
  491.         da = dr->dr_raddr;
  492.         dn = da->da_next;
  493.  
  494.         ap = arp_lookup(arpType, da->da_addr, iface);
  495.  
  496.         if((ap != NULLARP) && (ap->state == ARP_VALID)){
  497.             /* Host responded to arp.  Place address on used queue.
  498.              * Copy in physical address of host using address to
  499.              * make sure our info is up to date.  
  500.              * I could verify that physical address of host
  501.              * responding to  ARP matches the physical address of
  502.              * the host I think owns the address.  If don't match
  503.              * someone is probably using an incorrect address.
  504.              */
  505.  
  506.             q_remove(&dr->dr_reclaimq, (struct q_elt *)da);
  507.             --dr->dr_rcount;
  508.             da->da_time = now;        /* Time tested. */
  509.             memcpy(da->da_hwaddr, ap->hw_addr, (size_t)Arp_type[ap->hardware].hwalen);
  510.             q_enqueue(&dr->dr_usedq, (struct q_elt *)da);
  511.  
  512.         } else {
  513.             /* Host did not respond to ARP.  If addr on reclaim
  514.              * queue long enough, move it to the free queue.
  515.              */
  516.             if(now - da->da_time >= pendtime){
  517.                 q_remove(&dr->dr_reclaimq, (struct q_elt *)da);
  518.                 --dr->dr_rcount;
  519.                 q_enqueue(&dr->dr_freeq,(struct q_elt *)da);
  520.                 ++dr->dr_fcount;
  521.                 bp_log("Reclaimed address %s on net %s.\n", 
  522.                     inet_ntoa(da->da_addr), dr->dr_iface->name);
  523.             }
  524.         }
  525.     } else {
  526.         /* Use first addr in reclaimq. */
  527.         dn = (struct daddr *) dr->dr_reclaimq.head;
  528.     }
  529.     /*
  530.       * Now move to the next entry in the queue and ARP for it.
  531.       */
  532.      da = dn;
  533.     if(da != NULLDADDR){
  534.         ap = arp_lookup(arpType, da->da_addr, iface);
  535.         if(ap != NULLARP) arp_drop(ap);
  536.         res_arp(iface, arpType, da->da_addr, NULLBUF);
  537.     }
  538.     dr->dr_raddr = da;    /* Verify this address next time around. */
  539.     dr->dr_rtime = time(NULL);
  540. }
  541.  
  542.  
  543. /*
  544.  * Fill the reclaimation list from the used list.  Take addresses off the head
  545.  * of the used queue until the reclaim queue is full, the used queue is empty,
  546.  * or the address at the head of the used queue has been verified (responded
  547.  * to an ARP) within dr_time_addrretry tocks.
  548.  */
  549. static int
  550. da_fill_reclaim(dr)
  551. struct drange_desc *dr;
  552. {
  553.         struct daddr *da;
  554.         long now;
  555.  
  556.         now = time(NULL);
  557.  
  558.         while(dr->dr_rcount < RECLAIM_QUEUE_MAX){
  559.         /* Look at first address on used queue. */
  560.                 da = (struct daddr *) dr->dr_usedq.head;
  561.                 if(da == NULLDADDR)
  562.             return 0;    /* If used queue is empty, done filling. */
  563.                 if(now - da->da_time < dr->dr_time_addrretry)
  564.                         return 0;
  565.  
  566.         /* If the first element has responded to in ARP recently.
  567.          * I am done filling.
  568.          */
  569.         /* Get first address on used queue. */
  570.                 da = (struct daddr *) q_dequeue(&dr->dr_usedq);
  571.         /* Mark time addr put in reclaim queue. */
  572.                 da->da_time = now;
  573.         /* Put it at end of reclaim queue. */
  574.                 q_enqueue(&dr->dr_reclaimq,(struct q_elt *)da);
  575.                 ++dr->dr_rcount;
  576.         }
  577.         return 0;
  578. }
  579.  
  580.  
  581. /*
  582.  * Address assignment routines.
  583.  */
  584.  
  585. /*
  586.  * Assign an address.
  587.  */
  588. int
  589. da_assign(iface, hwaddr, ipaddr)
  590. struct iface *iface;    /* -> Pointer to lnet struct of net on which to assign addr. */
  591. char    *hwaddr;    /* -> Pointer to hardware address of hosts. */
  592. int32    *ipaddr;    /* <- Address assigned to host. */
  593. {
  594.     struct drange_desc *dr;    
  595.     struct daddr *da;    
  596.     int status;
  597.     struct arp_type    *at;
  598.  
  599.     /* Find the network table */
  600.     for(dr = (struct drange_desc *) rtabq.head; dr != NULLDRANGE; dr = dr->dr_next){
  601.         if(iface == dr->dr_iface)
  602.             break;    
  603.     }
  604.  
  605.     if(dr == NULLDRANGE){
  606.         *ipaddr = 0;
  607.         return ERR_NOIPADDRESS;
  608.     }
  609.  
  610.     /* If this host had an address assigned previously, try to reassign
  611.      * that. If no previous address, assign a new one.
  612.      */
  613.     status = da_get_old_addr(dr, hwaddr, &da);
  614.     if(status != 0) 
  615.         status = da_get_free_addr(dr, &da);
  616.     
  617.     /* If I got an address, assign it and link it in to the use list. */
  618.     if(status == 0){
  619.         memcpy(da->da_hwaddr, hwaddr, (size_t)dr->dr_hwaddrlen);
  620.         *ipaddr = da->da_addr;
  621.         da->da_time = time(NULL);    /* Time assigned */
  622.         q_enqueue(&dr->dr_usedq,(struct q_elt *)da);
  623.         at = &Arp_type[dr->dr_iface->type];
  624.         bp_log("IP addr %s assigned to %s on network %s\n",
  625.          inet_ntoa(*ipaddr),
  626.          (*at->format)(bp_ascii, hwaddr), dr->dr_iface->name);
  627.     }
  628.  
  629.         switch(dr->dr_rstate){
  630.         case R_OFF:
  631.         case R_DONE:
  632.                 if(dr->dr_fcount <= dr->dr_thon) 
  633.             da_enter_reclaim(dr);
  634.                 /* Fall through. */
  635.         case R_RECLAIM:
  636.                 if(dr->dr_fcount <= dr->dr_thcritical) 
  637.             da_enter_critical(dr);
  638.                 break;
  639.         /* case R_CRITICAL: is not handled. */
  640.         }
  641.         return status;
  642. }
  643.  
  644.  
  645. /*
  646.  * Enter the reclaimation state.
  647.  */
  648. static void
  649. da_enter_reclaim(dr)
  650. struct drange_desc *dr;
  651. {
  652.         char ipa[16], ipb[16];
  653.  
  654.         iptoa(dr->dr_start, ipa);
  655.         iptoa(dr->dr_end, ipb);
  656.  
  657.         if(dr->dr_rstate & R_OFF){
  658.                 dr->dr_vstate = V_SWAIT;  /* da_enter_reclaim: R_OFF */
  659.                 dr->dr_rtime = 0;
  660.         }
  661.         dr->dr_rstate = R_RECLAIM;
  662.         dr->dr_time_addrretry = TIME_ADDRRETRY;         /* Wait a while before retrying addresses. */
  663. }
  664.  
  665. /*
  666.  * Search for hwaddr on the used list, the reclaimation list, and the free list.
  667.  */
  668. static int
  669. da_get_free_addr(dr, dap)
  670. struct drange_desc *dr;
  671. struct daddr **dap;
  672. {
  673.         *dap = (struct daddr *) q_dequeue(&(dr->dr_freeq));
  674.         if(*dap == NULLDADDR) 
  675.         return ERR_NOIPADDRESS;
  676.         --dr->dr_fcount;
  677.  
  678.         return 0;
  679. }
  680.  
  681. /*
  682.  * Search for hwaddr on the used list, the reclaimation list, and the free list.
  683.  */
  684. static int
  685. da_get_old_addr(dr, hwaddr, dap)
  686. struct drange_desc *dr;
  687. char       *hwaddr;
  688. struct daddr **dap;
  689. {
  690.         struct daddr *da;
  691.  
  692.     /* Search the used queue */
  693.         for(da = (struct daddr *) dr->dr_usedq.head; da != NULLDADDR; da = da->da_next){
  694.                 if(memcmp(da->da_hwaddr, hwaddr, (size_t)dr->dr_hwaddrlen) == 0){
  695.                         q_remove(&dr->dr_usedq,(struct q_elt *)da);
  696.                         *dap = da;
  697.                         return 0;
  698.                 }
  699.         }
  700.  
  701.     /* Search the relaimq queue */
  702.         for(da = (struct daddr *) dr->dr_reclaimq.head; da != NULLDADDR; 
  703.         da = da->da_next){
  704.                 if(memcmp(da->da_hwaddr, hwaddr, (size_t)dr->dr_hwaddrlen) == 0){
  705.                         /* Here is the address.  I have to be carefull in removing it from
  706.              * reclaim queue, I may be verifying this address.
  707.                          * If I am, I have to fix up the pointers before removing this
  708.                          * element.
  709.                          */
  710.                         if((dr->dr_rstate & R_OFF) == 0 && dr->dr_vstate == V_VERIFY 
  711.                 && dr->dr_raddr == da){ 
  712.                 /* I am verifying this very address.  */
  713.                                 /* Start over.  
  714.                  * This should happen very infrequently at most. */
  715.                                 dr->dr_vstate = V_SWAIT;  /* get_old_addr */
  716.                         }
  717.                         q_remove(&dr->dr_reclaimq,(struct q_elt *)da);
  718.                         *dap = da;
  719.                         return 0;
  720.                 }
  721.         }
  722.  
  723.     /* Search the free queue */
  724.         for(da = (struct daddr *) dr->dr_freeq.head; da != NULLDADDR; da = da->da_next){
  725.                 if(memcmp(da->da_hwaddr, hwaddr, (size_t)dr->dr_hwaddrlen) == 0){
  726.                         q_remove(&dr->dr_freeq,(struct q_elt *)da);
  727.                         --dr->dr_fcount;
  728.                         *dap = da;
  729.                         return 0;
  730.                 }
  731.         }
  732.         return ERR_NOIPADDRESS;
  733. }
  734.  
  735. #ifdef    notdef
  736. static void
  737. dprint_dr_record(dr)
  738. struct drange_desc *dr;
  739. {
  740.         bp_log("Queue link   x%lx\n", dr->dr_next);
  741.         bp_log("Pointer to network information         x%lx\n", dr->dr_iface);
  742.         bp_log("First IP address in range              x%lx\n", dr->dr_start);
  743.         bp_log("Last IP address in range               x%lx\n", dr->dr_end);
  744.         bp_log("Number of IP addresses in range        %d\n", dr->dr_acount);
  745.         bp_log("Number of IP addresses in free         %d\n", dr->dr_fcount);
  746.         bp_log("Number of IP addresses on reclaimation queue %d\n", 
  747.         dr->dr_rcount);
  748.         bp_log("Threshold for turning on reclaimation  %d\n", dr->dr_thon);
  749.         bp_log("Threshold for critical reclaimation    %d\n", dr->dr_thcritical);
  750.         bp_log("Threshold for turning off reclaimation %d\n", dr->dr_thoff);
  751.         bp_log("Time to wait before retrying addresses %ld\n", 
  752.         dr->dr_time_addrretry);
  753.         bp_log("Length of hardware address             %d\n", dr->dr_hwaddrlen);
  754.         bp_log("Reclaimation state                     %d\n",(int)dr->dr_rstate);
  755.         bp_log("Verification state                     %d\n",(int)dr->dr_vstate);
  756.         bp_log("Time stamp for reclaimation            %ld\n", dr->dr_rtime);
  757.         bp_log("Address being verified                 x%lx\n", dr->dr_raddr);
  758.         bp_log("Pointer to table of addresses          x%lx\n", dr->dr_table);
  759.         bp_log("uesdq x%lx  reclaimq                   x%lx  freeq x%lx\n", dr->dr_usedq, 
  760.         dr->dr_reclaimq, dr->dr_freeq);
  761. }
  762. #endif
  763.  
  764.  
  765. /*
  766.  * Enter the critical reclaimation state.
  767.  */
  768. static void
  769. da_enter_critical(dr)
  770. struct drange_desc *dr;
  771. {
  772.         char ipa[16], ipb[16];
  773.     char *ipc;
  774.  
  775.     ipc = inet_ntoa(dr->dr_start);
  776.     strcpy(ipa, ipc);
  777.     ipc = inet_ntoa(dr->dr_end);
  778.     strcpy(ipb, ipc);
  779.  
  780.         if((dr->dr_rstate & R_OFF) == 0){
  781.                 dr->dr_vstate = V_SWAIT;    /* Enter critical, & R_OFF */
  782.                 dr->dr_rtime = 0;
  783.         }
  784.         dr->dr_rstate = R_CRITICAL;
  785.         dr->dr_time_addrretry = 0;      /* Retry addresses as fast as possible. */
  786. }
  787.  
  788. /*
  789.  * Initialization    
  790.  */
  791. /*
  792.  * Initialize the Dynamic address assignment module.
  793.  */
  794. int
  795. da_init()
  796. {
  797.         q_init(&rtabq);
  798.         return 0;
  799. }
  800.  
  801. /*
  802.  * Begin dynamic address service for a network.
  803.  */
  804. int
  805. da_serve_net(iface, rstart, rend)
  806. struct iface *iface;        /* Pointer to lnet record. */
  807. int32 rstart;            /* First address in range. */
  808. int32 rend;            /* Last address in range. */
  809. {
  810.     struct drange_desc *dr;    /* Pointer to the range descriptor. */
  811.     struct daddr *da;    /* Pointer to an address structure. */
  812.     int32 rcount;        /* Number of addresses range. */
  813.     time_t now;        /* Current time. */
  814.     int16 i;
  815.     char ipc[16], ipd[16];
  816.  
  817.         /* Find the network table */
  818.         for(dr = (struct drange_desc *) rtabq.head; dr != NULLDRANGE;
  819.      dr = dr->dr_next){
  820.                 if(iface == dr->dr_iface)
  821.                         break;
  822.         }
  823.  
  824.     
  825.     if(dr == NULLDRANGE){
  826.         /* If there is no network table, allocate a new one
  827.          *
  828.           * Allocate the memory I need.
  829.           */
  830.         dr = (struct drange_desc *) calloc(1, sizeof(*dr));
  831.         if(dr == NULLDRANGE) 
  832.             return E_NOMEM;
  833.     } else if((dr->dr_start != rstart) || (dr->dr_end != rend)) 
  834.         /* If the range is different, create a new range */
  835.         free(dr->dr_table);
  836.     else
  837.         return 0; /* There is no change, return */
  838.  
  839.  
  840.     rcount = (rend - rstart) + 1;
  841.     da = (struct daddr *) calloc(1,(sizeof (*da) + iface->iftype->hwalen) * rcount);
  842.     if(da == NULLDADDR) 
  843.         return E_NOMEM;
  844.  
  845.     /* 
  846.      * Got the memory, fill in the structures.
  847.      */
  848.     dr->dr_iface = iface;
  849.     dr->dr_start = rstart;
  850.     dr->dr_end = rend;
  851.     dr->dr_acount = rcount;
  852.     dr->dr_fcount = 0;
  853.     dr->dr_rcount = 0;
  854.     dr->dr_thon = (rcount * THRESH_ON) / 100;
  855.     dr->dr_thcritical = THRESH_CRITICAL;
  856.     dr->dr_thoff = (rcount * THRESH_OFF) / 100;
  857.     dr->dr_time_addrretry = 0;
  858.         dr->dr_hwaddrlen = iface->iftype->hwalen;
  859.     dr->dr_rstate = R_OFF;
  860.     dr->dr_vstate = V_SWAIT;            /* Initialize */
  861.     dr->dr_rtime = 0;
  862.     dr->dr_raddr = NULLDADDR;
  863.     dr->dr_table = da;
  864.  
  865.     /* 
  866.      * Fill in the table and link them all onto the used list.
  867.      */
  868.     time(&now);
  869.     for(i = 0, da = dr->dr_table; i < dr->dr_acount; ++i, da = da_getnext(dr, da)){
  870.         da->da_addr = rstart++;
  871.         da->da_time = 0;        /* Initiallize at 0, only here */
  872.         q_enqueue(&dr->dr_usedq,(struct q_elt *)da);
  873.     }
  874.     /* and set up the timer stuff */
  875.     if(rtabq.head == NULLCHAR){
  876.         set_timer(&da_timer,TIME_RWAIT*1000L);
  877.                da_timer.func = da_runtask;
  878.                da_timer.arg = (void *) 0;
  879.         start_timer(&da_timer);
  880.     }
  881.     q_enqueue(&rtabq,(struct q_elt *)dr);
  882.     da_enter_critical(dr);    /* Start reclaiming some of these addresses. */
  883.  
  884.     iptoa(dr->dr_start, ipc);
  885.     iptoa(dr->dr_end, ipd);
  886.     bp_log("DynamicIP range: %s - %s\n", ipc, ipd);
  887.     return 0;
  888. }
  889.  
  890.  
  891. /*
  892.  * Routines to implement a simple forward linked queue.
  893.  */
  894.  
  895. /*
  896.  *      q_init()
  897.  *      Initialize simple Q descriptor
  898.  */
  899. static void
  900. q_init(queue)
  901. struct q *queue;
  902. {
  903.         queue->head = 0;
  904.         queue->tail = 0;
  905. }
  906.  
  907.  
  908. /*
  909.  *      q_enqueue()
  910.  *              Enqueue an element in a simple Q.
  911.  */
  912. void
  913. q_enqueue(queue, elem)
  914. struct q *queue;
  915. struct q_elt *elem;
  916. {
  917.         struct q_elt *last;
  918.  
  919.         if(queue->tail != NULLCHAR){  /* If not empty Q... */
  920.                 last = (struct q_elt *) queue->tail;
  921.                 last->next = elem;
  922.         }
  923.         else
  924.         queue->head = (char *) elem;
  925.  
  926.         queue->tail = (char *) elem;
  927.         elem->next = NULLQ_ELT;
  928. }
  929.  
  930.  
  931. /*
  932.  *      q_dequeue       ()
  933.  *      Pull an element off of the head of a Q.
  934.  */
  935. struct q_elt *
  936. q_dequeue(queue)
  937. struct q *queue;
  938. {
  939.         struct q_elt *elem;
  940.  
  941.         if(queue->head == NULLCHAR)
  942.         return NULLQ_ELT; /* return NULL when empty Q */
  943.         elem = (struct q_elt *) queue->head;
  944.         queue->head = (char *) elem->next;
  945.         elem->next = NULLQ_ELT;
  946.         if(queue->head == NULLCHAR)
  947.         queue->tail = NULLCHAR;
  948.         return elem;
  949. }
  950.  
  951.  
  952. /*
  953.  *      Remove an element from the middle of a queue.  Note that
  954.  *      there is no mutex here, so this shouldn't be used on
  955.  *      critical Qs
  956.  */
  957.  
  958. static int
  959. q_remove(source_queue, qel)
  960. struct q *source_queue;
  961. struct q_elt *qel;
  962. {
  963.         struct q_elt *prev, *e;
  964.  
  965.         /*   Case : removing first in Q */
  966.  
  967.         if(qel == (struct q_elt *) source_queue->head){
  968.                 source_queue->head = (char *)qel->next;  /* trying to remove first in queue... */
  969.                 if(source_queue->head == NULLCHAR)      /* nothing left... */
  970.                         source_queue->tail = NULLCHAR;     /* blank out the Q */
  971.                 else if(source_queue->head == source_queue->tail){ /* One thing left */
  972.                         e = (struct q_elt *) source_queue->head; /* As insurance, set it's next to NULL. */
  973.                         e->next = NULLQ_ELT;
  974.                 }
  975.                 return 0;
  976.         }
  977.  
  978.         /* find Q element before qel, so that we can link around qel */
  979.         for(prev = (struct q_elt *) source_queue->head; prev->next != qel; prev = prev->next)
  980.                 if(prev == NULLQ_ELT)
  981.                         return 1;
  982.  
  983.         /* Case : Removing last in Q */
  984.  
  985.         if(qel == (struct q_elt *) source_queue->tail){     /* trying to remove last one in queue... */
  986.                 prev->next = NULLQ_ELT;   /* there is a prev elt, since we return on first */
  987.                 source_queue->tail = (char *) prev;
  988.                 return 0;
  989.         }
  990.  
  991.         /*  else, removing a queue element in the middle...  */
  992.         prev->next = qel->next;
  993.         return 0;
  994. }
  995.  
  996. /*
  997.  * Support Routines
  998.  */
  999.  
  1000. static void
  1001. iptoa(ipaddr, ipstr)
  1002. int32 ipaddr;
  1003. char ipstr[16];
  1004. {
  1005.     char *tmpStr;
  1006.  
  1007.     tmpStr = inet_ntoa(ipaddr);
  1008.     strcpy(ipstr, tmpStr);
  1009. }
  1010.  
  1011.  
  1012. #ifdef    notdef
  1013. static  void
  1014. build_hex_string(fromstr, len, tostr)
  1015. char *fromstr; int  len;
  1016. char *tostr;
  1017. {
  1018.     int i;
  1019.  
  1020.     for(i=0; i < len; i++){
  1021.         sprintf(tostr, "%02x", fromstr[i]);
  1022.         tostr++;
  1023.         tostr++;
  1024.     }
  1025.     fromstr[len] = 0;
  1026. }
  1027. #endif
  1028.